package 题目集.滑动窗口.ch02_不定长窗口;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/max-consecutive-ones-iii/description/
 * 给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。
 */
public class demo08_最大连续1的个数 {

    /**
     * 第一思路：枚举数组中每个0翻或不翻的情况，枚举复杂度O(2^n)，找到其最大连续1的数量O(n)，总体复杂度O(n*2^n)
     * 第二思路，二分{@link 题目集.二分.demo08_最大连续1的个数#longestOnes(int[], int)}：
     * 二分长度，设长度为m，验证是否存在长度为m且符合条件的区间。验证的方式是查看该区间内0的个数<=k,这个可以通过前缀和快速得到
     * 第三思路：滑动窗口，把问题转换一下，相当于找0个数<=k的最长窗口。
     */
    public int longestOnes(int[] nums, int k) {
        int ans = 0;
        int cnt = 0;    //窗口内0的个数
        for (int i = 0, j = 0; j < nums.length; j++) {
            cnt += 1 - nums[j];
            while (cnt > k) {
                cnt -= 1 - nums[i++];
            }
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }

    @Test
    public void t1() {
        int[] nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        int k = 2;
        System.out.println(longestOnes(nums, k));
    }
}
